package com.github.yangyishe.p100;

/**
 * 28. 找出字符串中第一个匹配项的下标
 * https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：haystack = "sadbutsad", needle = "sad"
 * 输出：0
 * 解释："sad" 在下标 0 和 6 处匹配。
 * 第一个匹配项的下标是 0 ，所以返回 0 。
 * 示例 2：
 *
 * 输入：haystack = "leetcode", needle = "leeto"
 * 输出：-1
 * 解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
 *
 *
 * 提示：
 *
 * 1 <= haystack.length, needle.length <= 104
 * haystack 和 needle 仅由小写英文字符组成
 */
public class Problem28 {
    public static void main(String[] args) {
        String haystack="aabaaabaaac";
        String needle="aaac";
        // caacbcaaca
        // cadacbcadaca

        Problem28 problem28 = new Problem28();
        int i = problem28.strStr(haystack, needle);
        System.out.println(i);
    }

    public int strStr(String haystack, String needle){

        // 构建匹配值表
        // pi: 前缀匹配值表, 表示第i个字符及其前面构建的长度为pi[i]长度的字符串, 是needle的前缀(且下标是第pi[i]-1)
        // i: 依次遍历needle的每个字符
        // j: 通常表示首字母偏移量, 用以与needle.charAt(i)比较
        int[] pi=new int[needle.length()];
        for(int i=1,j=0;i<needle.length();i++){
            // 如果没有此循环, 则j就等于左邻下标的匹配值
            while(j>0&&needle.charAt(i)!=needle.charAt(j)){
                // 在构建匹配值表的内部, 使用匹配值表
                // 以"caacbcaaca"为例, 访问到i=8时,字符为c, 前面的匹配值表为[0,0,0,1,0,1,2,3,4]
                // 此时访问i=9.j=5, 由于'a'!=='b',故j=pi[4]=1
                // 再比较i=9,j=1,由于'a'=='a',所以pi[9]=1+1=2
                // 再以"cadacbcadaca"为例, 访问到i=10时, 字符为c, 前面的匹配值表为[0,0,0,0,1,0,1,2,3,4,5]
                // 此时访问i=11, j=5, 由于'a'!='b', j=pi[5-1]=1
                // 再比较i=11,j=1, 由于'a'=='a',故j=1+1=2

                // 进入次循环, 表示要找到一个次小的匹配前缀(找到次小的匹配值就等于找到次小的匹配前缀, 也等于找到次小的匹配后缀)
                // 本代码中, 谈到前缀, 后缀, 都是真前缀, 真后缀. 即不考虑自身. 前缀不能包含最后一位; 后缀不能包含第一位.
                // 如此, 要找次小的匹配前缀(后缀), 直接思路是, 把当前左邻后缀对应的最大匹配传砍掉第一位. 如此, 就等同于, 在原来的最大匹配前缀(后缀)内部, 去找一个最大匹配前缀(后缀)
                // 而这个步骤, 恰好与在前next[j-1]个字符构成的字符串内找最大匹配前缀(后缀)是一样的.
                // 如此, 就继续对比次小前缀后缀的后一位, 看与当前字符串是否相等即可
                // 如果相等, 则就是继续往下走的路子
                // 如果不相等, 则继续在次小的匹配前缀(后缀)中, 找更小的
                j=pi[j-1];
            }

            if(needle.charAt(i)==needle.charAt(j)){
                j++;
            }
            pi[i]=j;

        }

        // 2. 遍历内容字符串
        int cindex=0;
        int kindex=0;
        char[] needleChars = needle.toCharArray();
        char[] contentChars = haystack.toCharArray();
        while(cindex<haystack.length()&&kindex<needle.length()){
            if(contentChars[cindex]==needleChars[kindex]){
                kindex++;
            }else if(kindex>0){
//                cindex-=matchArr[kindex];
                kindex=pi[kindex-1];
                continue;
            }

            cindex++;
        }

        return kindex==needle.length()?cindex-kindex:-1;
    }

    /**
     * 使用KMP算法
     * 1. 获取关键字的匹配值表, 即前缀匹配值表
     * 2. 遍历内容字符串. 如果不同则继续走下一个下标; 如果相同, 则开始进行比较. 在比较过程中, 如果发现某个字符串不匹配, 则根据匹配值, 使当前索引回退匹配值对应的位数
     *
     * @param haystack
     * @param needle
     * @return
     */
    public int strStrKmp1(String haystack, String needle) {
        // 1. 匹配值表
        int[] matchArr=new int[needle.length()];
        // 构建前置字符串
        String[] prefixs=new String[needle.length()-1];
        for(int i=0;i<needle.length()-1;i++){
            prefixs[i]=needle.substring(0,i+1);
        }
        int pos=0;
        char[] needleChars = needle.toCharArray();
        for(int i=1;i<needleChars.length-1;i++){
            if(needleChars[pos]==needleChars[i]){
                pos++;
                matchArr[i]=pos;
                continue;
            }
            while(pos>0){
                // 如果偏移大于0, 除了比前置字符串的匹配大1的情况
                if (prefixs[pos-1].equals(needle.substring(i+1-pos,i+1))) {
                    matchArr[i]=pos;
                    break;
                }
                pos--;
            }

            if(matchArr[i]==0&&needleChars[0]==needleChars[i]){
                pos++;
                matchArr[i]=pos;
            }

        }

        // 2. 遍历内容字符串
        int cindex=0;
        int kindex=0;
        char[] contentChars = haystack.toCharArray();
        while(cindex<haystack.length()&&kindex<needle.length()){
            if(contentChars[cindex]==needleChars[kindex]){
                kindex++;
            }else if(kindex>0){
//                cindex-=matchArr[kindex];
                kindex=matchArr[kindex-1];
                continue;
            }

            cindex++;
        }

        return kindex==needle.length()?cindex-kindex:-1;
    }
}
